#include "ListNode.h"
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;

// 547
void dfs(vector<vector<int>> &matrix, vector<bool> visited, int i)
{
    for (int j = 0; j < matrix.size(); j++)
    {
        if (matrix[i][j] == 1 && !visited[j])
        {
            visited[j] = true;
            dfs(matrix, visited, j); //从这里开始下探
        }
    }
}
int findCircleNum(vector<vector<int>> isConnected)
{
    vector<bool> visited(isConnected.size(), 0);
    int res = 0;
    for (int i = 0; i < isConnected.size(); i++)
    {
        if (visited[i])
            continue;
        else
        {
            dfs(isConnected, visited, i);
            res++;
        }
    }
    return res;
}

int getMinLength(vector<vector<int>> triangle)
{
    for (int i = triangle.size() - 2; i >= 0; i--)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
            triangle[i][j] += min(triangle[i][j + 1], triangle[i + 1][j + 1]);
        }
    }
    return triangle[0][0];
}

int rob(vector<int> houses)
{
    if (houses.size() == 0)
        return 0;
    if (houses.size() == 1)
        return houses[0];
    vector<int> dp(houses.size());
    dp[0] = 0;
    dp[1] = houses[0];
    for (int i = 2; i < houses.size(); i++)
    {
        dp[i] = max(dp[i - 1], houses[i] + dp[i - 2]);
    }
    return dp[dp.size() - 1];
}

bool searchMatrix(vector<vector<int>> &matrix, int target)
{
    if (matrix.size() == 0 || matrix[0].size() == 0)
        return false;
    int row = 0, col = matrix[0].size() - 1;
    while (row < matrix.size() && col >= 0)
    {
        if (matrix[row][col] < target)
            row++;
        else if (matrix[row][col] > target)
            col--;
        else
            return true;
    }
    return false;
}

ListNode *deleteDuplicate(ListNode *head)
{
    // double pointers
    ListNode *p = new ListNode(0);
    p->next = head;
    head = p;
    ListNode *left, *right;
    while (p->next)
    {
        left = p->next;
        right = left;
        while (right->next && right->next->val == left->val)
        {
            right = right->next;
        }
        if (left == right)
            p = p->next;
        else
            p->next = right->next;
    }
    return head->next;
}

int main()
{
    cout << "Hello World!" << endl;
    vector<int> houses{1, 2, 3, 1, 4, 5};
    time_t start=clock();
    for(int i=0;i<24;i++){
        start=clock();
    }
    return 0;
}